package structureDeDonnee;

import java.util.Iterator;

/**
 * liste iterable de cellule permetant un ajout de cellule en fin de liste en O(1) et 
 * l'ajout de liste en 0(n) (pour peu qu'elle soit trié) 
 */
public class MyList implements Iterable<Cell> {


	/**
	 * classe interne gérant les iterators MyList
	 * @see Iterator
	 */
	class MyIterator implements Iterator<Cell> {

		/**
		 * Maillon correspondant au curseur de l'itérateur
		 */
		private Maillon m;

		/**
		 * renvoie un itérateur sur la liste passée en paramètre
		 * 
		 * @param l
		 *            la liste passée en paramètre
		 */
		public MyIterator(MyList l) {
			m = l.head;
		}

		@Override
		public boolean hasNext() {
			return this.m != null;
		}

		@Override
		public Cell next() {
			Cell c = this.m.getValue();
			this.m = this.m.next;
			return c;
		}

		@Override
		public void remove() {
			assert (false) : "Not implemented yet";
		}

	}

	/**
	 * classe interne gérant les maillons de l'objet MyList
	 * 
	 * @author bruno
	 * 
	 */
	class Maillon {

		/**
		 * la valeur du Maillon
		 */
		public Cell value;

		/**
		 * référence vers le maillon suivant
		 */
		public Maillon next;

		@Override
		public String toString() {
			return "Maillon [value=" + value.toString() + "]" + "\n";
		}

		/**
		 * constructeur d'un maillon avec une cellule, mets la référence vers le
		 * maillon suivant à null
		 * 
		 * @param c
		 *            la cellule que prendra this.value pour valeur
		 */
		public Maillon(Cell c) {
			this.value = c;
			this.next = null;
		}

		/**
		 * constructeur d'un maillon avec une cellule, mets la référence vers le
		 * maillon suivant au maillon passé en paramètre
		 * 
		 * @param c
		 * @param m
		 */
		public Maillon(Cell c, Maillon m) {
			this.value = c;
			this.next = m;
		}

		/**
		 * getter de this.value
		 * 
		 * @return this.value
		 */
		public Cell getValue() {
			return value;
		}

		/**
		 * setter de this.value
		 * 
		 * @param value
		 *            la valeur que l'on affectera a this.value
		 */
		public void setValue(Cell value) {
			this.value = value;
		}

		/**
		 * getter de this.next
		 * 
		 * @return this.next
		 */
		public Maillon getNext() {
			return next;
		}

		/**
		 * setter de this.next
		 * 
		 * @param next
		 *            la valeur que l'on affectera a this.next
		 */
		public void setNext(Maillon next) {
			this.next = next;
		}
	}

	/**
	 * Maillon en tête de la liste
	 */
	public Maillon head;

	/**
	 * Maillon en bout de liste, permet a l'opération add de s'effectuer en O(1)
	 */
	public Maillon tail;

	/**
	 * constructeur par défaut, mets tout les champs à null
	 */
	public MyList() {
		head = null;
		tail = null;
	}

	/**
	 * Construit une MyList avec un maillon passé en paramètre
	 * 
	 * @param m
	 *            le maillon
	 */
	public MyList(Maillon m) {
		this.head = m;
		Maillon tmp = this.head;
		while (tmp.next != null) {
			tmp = tmp.next;
		}
		this.tail = tmp;
	}

	/**
	 * construit une MyList avec 2 maillons passés en paramètre correspondant
	 * respectivement à la tête et la queue
	 * 
	 * @param m
	 * @param m2
	 */
	public MyList(Maillon m, Maillon m2) {
		this.head = m;
		this.tail = m2;
	}

	/**
	 * opération d'ajout d'une Cellule a la fin de MyList
	 * 
	 * @param c
	 *            la cellule a ajouté
	 */
	public void add(Cell c) {
		add(new Maillon(c));
	}

	/**
	 * opération d'ajout d'un Maillon a MyList
	 * 
	 * @param m
	 *            le maillon à ajouter
	 */
	private void add(Maillon m) {
		if (isEmpty()) {
			this.head = m;
			this.tail = m;
		} else {
			this.tail.setNext(m);
			Maillon tmp = this.tail;
			while (tmp.next != null) {
				tmp = tmp.next;
			}
			this.tail = tmp;
		}
	}
	
	/**
	 * insere une cellule dans la liste de manière à garder 
	 * la liste trié 
	 * @param c cellule à ajouter
	 */
	public void inserer(Cell c) {
		Maillon m = new Maillon(c);		
		if (isEmpty()) { //si la liste est vide 
			this.head = m;
			this.tail = m;
		    return;
		}// sinon si l'element à inserer est plus petit que le premiere 
		//element de la liste
		else if(this.head.value.compareTo(c)<=0){
			m.next = this.head;
			this.head = m;
			return;
		}
		
		//sinon on parcoure la liste
		Maillon tmp = this.head;
		while(tmp.next!=null){
			if(tmp.next.value.compareTo(c)<=0){
				m.next = tmp.next;
				tmp.next = m;
			return;
			}
			tmp=tmp.next;
		}
		//sinon on l'ajoute en fin de liste 
		tmp.next=m;
		this.tail = m;
	}

	/**
	 * dit si la MyList est vide ou pas
	 * 
	 * @return true si elle est vide, false sinon
	 */
	public boolean isEmpty() {
		return this.head == null;
	}


	@Override
	public String toString() {
		StringBuffer s = new StringBuffer();
		Maillon tmp = this.head;
		while (tmp != null) {
			s.append(tmp.toString());
			tmp = tmp.next;
		}
		// s.append("tete : " + head.toString() + "  queue : " +
		// tail.toString());
		return s.toString();
	}

	/**
	 * retourne la taille de la MyList
	 * 
	 * @return
	 */
	public int length() {
		Maillon tmp = this.head;
		int ret = 0;
		while (tmp != null) {
			tmp = tmp.next;
			ret++;
		}
		return ret;
	}

	/**
	 * renvoie un iterator sur la MyList appelante
	 * 
	 * @return l'iterator
	 */
	public Iterator<Cell> iterator() {
		return new MyIterator(this);
	}

	/**
	 * Opération d'addition de deux MyList triés, celle appelante et celle passée en
	 * argument en O(n) 
	 * 
	 * @param arg
	 *            la MyList a ajouté à this
	 * @return la nouvelle MyList
	 */
	public MyList addAll(MyList arg) {
		// Cette méthode fonctionne comme suit:
		// on récupère le maillon (resp m1 et m2) sur chacune des MyList
		// ensuite a chaque étape on va comparer la valeur
		// renvoyée par la méthode MyIterator.next()
		// si la valeur renvoyée par m1.value est plus petite (testé avec une
		// méthode compareTo())
		// que celle
		// renvoyée par m2.value alors on ajoute la valeur renvoyée par m1.value
		// a la MyList
		// qu'on retournera, et vice versa, lorsque les deux valeurs sont
		// égales, on ajoute
		// alors une Cellule a la MyList qui sera retourné ayant pour poids la
		// somme des poids de
		// m1.value et m2.value
		// Précision : quand je parle de première liste, je fais référence a
		// this
		// quand je parle de deuxième liste je fais réference a arg

		MyList liste = new MyList(); // la liste que l'on retournera
		if (this != null && arg != null) { // si aucune des deux listes est null
			Maillon m1 = this.head;
			Maillon m2 = arg.head;
			boolean continuer = false;
			Cell tmp1 = null;
			Cell tmp2 = null;
			if (m1 != null) {
				tmp1 = m1.value;
				continuer = true;
			}
			if (m2 != null) {
				tmp2 = m2.value;
				continuer = true;
			}
			while (continuer) { // tant qu'on a pas "épuisé" les deux listes
				// System.out.println(liste.toString());
				if (tmp1 != null && tmp2 != null) { // aucune des deux listes
													// est "épuiséeé
					if (tmp1.compareTo(tmp2) > 0) { // la valeur de m1 est plus
													// petite que celle de m2
						// System.out.println("je suis en 1)");
						// on ajoute alors la cellule de m1.value
						liste.add(new Maillon(new Cell(tmp1.getPoids(), tmp1
								.getPosition()), null));
						m1 = m1.next; // et on récupère le maillon suivant
						if (m1 != null) {
							tmp1 = m1.value;
						} else {
							tmp1 = null;
						}
					} else if (tmp1.compareTo(tmp2) < 0) { // cas inverse
															// (m2.value>m1.value)
						// System.out.println("je suis en 2)");
						liste.add(new Maillon(new Cell(tmp2.getPoids(), tmp2
								.getPosition()), null));
						m2 = m2.next;
						if (m2 != null) {
							tmp2 = m2.value;
						} else {
							tmp2 = null;
						}
					} else { // si les deux cellules sont égales
						// System.out.println("je suis en 3)");
						// on ajoute une cellule avec la même position et un
						// poids égal a la somme des poids des 2 cellules
						liste.add(new Maillon(new Cell(tmp1.getPoids()
								+ tmp2.getPoids(), tmp1.getPosition()), null));
						m1 = m1.next;
						if (m1 != null) {
							tmp1 = m1.value;
						} else {
							tmp1 = null;
						}
						m2 = m2.next;
						if (m2 != null) {
							tmp2 = m2.value;
						} else {
							tmp2 = null;
						}
					}
				} else if (tmp1 == null && tmp2 != null) { // on a épuisé la
															// première liste
					// mais pas la deuxième
					// System.out.println("je suis en 4)");
					// on concatène alors ce qu'il reste de la deuxieme liste a
					// la liste a retourner
					liste.add(new Maillon(new Cell(tmp2.getPoids(), tmp2
							.getPosition()), m2.next));
					continuer = false; // pour sortir de la boucle
				} else if (tmp2 == null && tmp1 != null) {
					// cas ou on a épuisé la deuxième liste et pas la première
					// System.out.println("je suis en 5)");
					// on concatène alors ce qu'il reste de la première liste a
					// la liste a retourner
					liste.add(new Maillon(new Cell(tmp1.getPoids(), tmp1
							.getPosition()), m1.next));
					continuer = false;
				} else {
					continuer = false;
				}
			}
			// System.out.println(liste.toString()+"\n\n\n");
			return liste; // on retourne la nouvelle MyList
		} else if (this != null && arg == null) {
			// si la deuxieme MyList est null et pas la première alors
			// l'addition
			// revient a renvoyer la première
			return this;
		} else if (this == null && arg != null) {
			// cas inverse
			return arg;
		} else {
			// cas ou les deux sont null on renvoie alors null
			return null;
		}
	}

	/**
	 * 
	 * @return la première cellule de MyList
	 */
	public Cell getPremiereCellule() {
		if (this.head != null) {
			return this.head.value;
		}
		return null;
	}
	
	/**
	 * 
	 * @return la dernière cellule de MyList
	 */
	public Cell getDerniereCellule() {
		if (this.tail != null) {
			return this.tail.value;
		}
		return null;
	}

	/**
	 * Dit si une cellule est contenue dans la MyList appelante
	 * 
	 * @param c
	 *            la cellule a tester
	 * @return true si elle est contenue, false sinon
	 */
	public boolean contains(Cell c) {
		if (this.head == null) {
			return false;
		} else {
			Maillon tmp = this.head;
			while (tmp != null) {
				if (tmp.value.equals(c)) {
					return true;
				} else {
					tmp = tmp.next;
				}
			}
		}
		return false;
	}

	/**
	 * Permet de trier les cellules, afin d'avoir de les avoir de haut en bas et
	 * de gauche a droite
	 * 
	 * @return la liste triée
	 */
	public MyList sort() {
		/*
		 * c'est un algorithme de complexité O(n²) On va chercher a chaque
		 * tour la cellule la plus en haut et la plus a gauche, l'ajouter a la
		 * liste a retourner et enlever la cellule en question de la liste
		 * initiale
		 */
		MyList retour = new MyList();
		Maillon tmp = this.head;
		Maillon min = this.head;
		Maillon tmpPrec = null;
		Maillon minPrec = null;
		while (tmp != null) { // tant qu'on a pas fini de parcourir la liste
								// initiale
			while (tmp != null) { // on chercher le minimum
				int resCompareTo = min.value.compareTo(tmp.value);
				if (resCompareTo == -1) {
					min = tmp;
					minPrec = tmpPrec;
				}
				tmpPrec = tmp;
				tmp = tmp.next;
			}
			// On enleve le maillon en question de la liste
			if (minPrec == null) { // cas ou le minimum est en tete de la liste
				this.head = min.next;
			} else {
				minPrec.next = min.next;
			}
			retour.add(min.value); // on ajoute la cellule du maillon enlevé
			// dans la liste a retourner
			tmp = this.head;
			min = this.head;
			tmpPrec = null;
			minPrec = null;
		}
		return retour;
	}

	/**
	 * renvoie une MyList identique a celle appelante
	 * @return la liste clonée
	 */
	public MyList clone() {
		Maillon tmp = this.head;
		MyList clone = new MyList();
		while (tmp != null) {
			clone.add(tmp.value);
			tmp = tmp.next;
		}
		return clone;
	}

}
